% !Mode:: "TeX:UTF-8"

\chapter{基于CRF的初等数学命名实体识别算法}

通过之前的讨论，我们能够看出基于CRF的初等命名实体识别效果将是较好的。因此我们在此基础上设计了基于CRF的初等数学命名实体识别算法。

\section{总体设计}

\pic [htbp]{总体设计流程示意图}{width=0.6\textwidth}{Process}

\subsection{总体实验流程设计}

想要完成命名实体识别的识别实验工作，最首要的工作应该是收集大量未标注处理过得相关领域语料。然后对语料进行预处理：（1）除错，由于语料来源不稳定，除错步骤需要尽量去除多余字、错字。（2）修改格式和数据合并。接着通过研究当前环境的语言特点以及应用场合，合理安排标注集合，并对数据进行人工标注。第四步，对数据集合进行切分，分为训练集与测试集合。第五步，构建测试平台并训练测试，统计结果并分析。整体设计流程图如\ref{Process}所示。

\subsection{实验环境搭建}

由于CRF模型已经有非常多的实现，并不需要自己编码完成。考虑到参考资料和稳定性等因素，选择了CRF++作为实验软件。由于有相当多的预处理工作，应选择一种易用方便的语言作为处理工具使用，在此我设计使用Python作为处理语言。Python是一种面对对象的解释型语言，目前世界范围内广泛使用的版本是2.0和3.0系列，两种语言版本兼容性不完美，因此通常我们使用其中某一个版本。出于方便考虑，选择了Python3.5作为处理工具的编程语言，为了能够良好的管理代码，使用了Git作为版本管理工具。为了防止Python多个版本产生冲突，使用了Virtualenv作为Python运行的虚拟环境。综上所述，最终使用的实验环境如表\ref{environment}

\threelinetable[htbp]{environment}{0.4\textwidth}{lcr}{实验环境}
{项目&名称&版本\\}
{
操作系统 & Ubuntu  & 16.04 \\
编程语言 & Python & 3.5.2 \\
虚拟环境 & Virtualenv & - \\
算法软件 & CRF++ & 0.58 \\
}
{
}

\section{详细实验流程}

\subsection{CRF++软件的安装与使用方法分析}
为了能够尽量减少无用工作，首先安装CRF++软件并对其使用过程，数据格式要求有明确的认识是必要的。

\subsubsection{CRF++的编译与安装}
在安装了GCC等工具，在Github得到了软件的源代码。根据参考源代码中说明网页，使用make工具进行第一次编译，发生了缺少链接的库的错误。检查错误后，参考Github页面上issue分页，执行命令：

尝试编译得到了crflearn和crftest软件。

\subsubsection{训练及测试数据集合格式}

参考源代码包中example文件夹，可以看见其中有四份例子。结合文档，可以掌握训练和测试的方法。CRF++使用的训练数据集和测试数据集的格式如下。
\threelinetable[htbp]{traindataformat}{0.4\textwidth}{lcr}{训练数据集数据格式}
{观察序列&词性&语法树\\}
{
Confidence &NN &B-NP\\
in & IN & B-PP\\
the & DT& B-NP\\
pound & NN & I-NP\\
is & VBZ & B-VP\\
widely & RB & I-VP\\
expected &VBN & I-VP\\
to & TO & I-VP\\
take & VB & I-VP\\
another & DT & B-NP\\
}
{
}

如表格\ref{traindataformat}所示，示例中训练数据集由三列组成，第一列为观察序列，也就是单词或单字；第二列为第一列单词所对应的词性；第三列表示了此句子的语法结构。可以轻而易举地看出，此数据集训练出的模型将会解决英文句子的语法分析任务。在机器学习领域，有监督学习输入数据为一个特征向量和一个标签，在此例子中即为第一列的观察序列和第二列的词性，标签为语法树。考虑我们的初等数学命名实体标注的任务，特征向量的第一个分量也将是观察序列，也就是输入的初等数学题的字符串，而第二个分量可以是单字对应的词性，而标签则应该是命名实体标签。

\subsubsection{特征模板文件}
本文在第二章介绍过，条件随机场模型在使用前应该制定好特征函数，在CRF++中，提供了特征模板作为一种方便的创建特征函数的方法。
本文先以CRF++提供的日文分词示例训练集以及特征模板文件为例子，详细解释分析特征模板的使用。

\threelinetable[htbp]{templateforjapan}{0.4\textwidth}{l}{CRF++中提供的一个特征模板}
{特征模板文件内容\\}
{
\# Unigram\\
U00:\%x[-2,0]\\
U01:\%x[-1,0]\\
U02:\%x[0,0]\\
U03:\%x[1,0]\\
U04:\%x[2,0]\\
U05:\%x[-2,0]/\%x[-1,0]/\%x[0,0]\\
U06:\%x[-1,0]/\%x[0,0]/\%x[1,0]\\
U07:\%x[0,0]/\%x[1,0]/\%x[2,0]\\
U08:\%x[-1,0]/\%x[0,0]\\                               
U09:\%x[0,0]/\%x[1,0]\\

\# Bigram\\
B\\
}
{
}

\threelinetable[htbp]{dataforjapan}{0.4\textwidth}{c}{日文分词任务训练数据集}
{训练数据集内容\\}
{
毎 k   B\\
日 k   I \\
新 k   I \\
聞 k   I \\
社 k   I \\
特 k   B \\
別 k   I \\
顧 k   B \\
問 k   I \\
４ n   B \\
}
{
}
如表\ref{templateforjapan}所示，在特征模板文件中，每一行代表一个特征，而其中每一个形如\%[-2,0]的内容，代表着一个宏，宏的结构为“\%[行偏移,列位置]”，代表了相对于当前指向的行的位置和列的绝对位置。比如说，扫描到第三行时，\%[-2,0]代表着“毎”这个日语汉字单个字特征。很显然，根据特征模板，从第一行扫描到第最后一行，生成许多特征，姑且设这个特征数目为\(L\)。我们又知道输出类型是第三列也就是标记，在此例子中只有B和I。假如说某个训练集合中，输出类型为N种。使用Unigram设计的特征模板将会生成\(L \times N\)个特征函数。其形式如表\ref{functions}

\threelinetable[htbp]{functions}{0.7\textwidth}{l}{特征函数集合示例}
{特征函数集合示例\\}
{
func1 = if (output = B and feature="U01:日") return 1 else return 0\\
func2 = if (output = I and feature="U01:日") return 1 else return 0\\
....\\
funcXX = if (output = B and feature="U01:問") return 1  else return 0\\
funcXY = if (output = I and feature="U01:問") return 1  else return 0\\
}
{
}

\subsection{未加工初等数学语料的获取及预处理}
互联网上有大量的中学数学题库可以使用，但手工下载收集工作量过大，因此使用了Python爬虫获得了大量的免费初等数学题，并进行人工初步筛选去除明显无法使用的文件，比如空文件；不包含答案的文件；乱码文件等。

由于获得的题库文件格式通常为Word，而训练CRF++的文件通常为UTF-8编码纯文本文档，因此选择使用python-doc库进行处理，去除了其中空文件和并仅仅抽取出题干。

利用工业上常用的分词及词性标注软件包jieba，对所有的数据进行了合并分词并标注了词性。效果如表\ref{jiebaresult}

\threelinetable[htbp]{jiebaresult}{0.4\textwidth}{c}{分词及标注后结果}
{分词及标注词性后文件内容\\}
{
一 m\\
个 q\\
工 n\\
厂 zg\\
有 v\\
若 c\\
干 v\\
个 q\\
车 zg\\
间 f\\
}
{
}

随后，本文根据第三章讨论得出的标注集合，对所有数据进行人工标注处理。处理后，由于人工标注难免出现错误，使用python正则表达式对所有的数据进行了格式错误检测。最终获得的数据集合效果如表\ref{findata}

\threelinetable[htbp]{findata}{0.4\textwidth}{c}{人工标注后的数据}
{标注命名实体后文件内容\\}
{
某 r O\\
单 n O\\
位 q O\\
有 v O\\
职 ng B-NAM\\
工 n E-NAM\\
7 x B-NUM\\
5 x I-NUM\\
0 x E-NUM\\
人 n S-UNI\\
， x O\\
其 r O\\
中 f O\\
青 ns B-NAM\\
年 m I-NAM\\
职 ng I-NAM\\
工 n E-NAM\\
3 x B-NUM\\
5 x I-NUM\\
0 x E-NUM\\
人 n S-UNI\\
}
{
}

\subsection{特征模板设计}
\subsubsection{原子特征}
原子特征可以描述当前词和前后连续两个词的词性和词形，能够表达有限的上下文信息。内容如表\ref{templateatomic}
\threelinetable[htbp]{templateatomic}{0.4\textwidth}{l}{原子特征模板}
{本文所用的部分特征模板\\}
{
U00:\%x[-2,0]\\
U01:\%x[-1,0]\\
U02:\%x[0,0]\\
U03:\%x[1,0]\\
U04:\%x[2,0]\\
U05:\%x[-2,1]\\
U06:\%x[-1,1]\\
U07:\%x[0,1]\\
U08:\%x[1,1]\\
U09:\%x[2,1]\\
}
{
}

\subsubsection{组合特征}
通过搭配词性和词形以及组合多词等手段，构造符合的非线性特征，形成了组合特征。内容如表\ref{templategroup}
\threelinetable[htbp]{templategroup}{0.4\textwidth}{l}{组合特征模板}
{本文所用的部分特征模板\\}
{
U10:\%x[0,0]/\%x[0,1]\\
U11:\%x[0,0]/\%x[-1,0]\\
U12:\%x[0,0]/\%x[1,0]\\
U13:\%x[0,1]/\%x[-1,0]\\
U14:\%x[0,0]/\%x[1,1]\\
U15:\%x[-1,0]/\%x[-1,1]\\
U16:\%x[-1,0]/\%x[-2,0]\\
U17:\%x[-2,0]/\%x[-2,1]\\
U18:\%x[1,0]/\%x[2,0]\\
U19:\%x[-1,0]/\%x[1,0]\\
U20:\%x[1,0]/\%x[0,1]\\
U21:\%x[-2,1]/\%x[-1,1]\\
U22:\%x[-2,1]/\%x[0,1]\\
U23:\%x[-1,1]/\%x[0,1]\\
U24:\%x[-1,1]/\%x[1,1]\\
U25:\%x[0,1]/\%x[1,1]\\
U26:\%x[0,1]/\%x[2,1]\\
U27:\%x[1,1]/\%x[2,1]\\
}
{
}

最后，将数据集拆分成训练集合和测试集合，使用训练集合对CRF++进行训练，并测试得到机器标注结果。如\ref{resultdatatemplate}
\threelinetable[htbp]{resultdatatemplate}{0.4\textwidth}{l}{机器标注结果}
{机器标注结果输出文件部分内容\\}
{
某	r	O	O\\
校	ng	O	O\\
有	v	O	O\\
高	a	B-NAM	B-NAM\\
级	q	I-NAM	I-NAM\\
教	v	I-NAM	I-NAM\\
师	ng	E-NAM	E-NAM\\
2	x	B-NUM	B-NUM\\
6	x	E-NUM	E-NUM\\
人	n	S-UNI	S-UNI\\
，	x	O	O\\
中	f	B-NAM	B-NAM\\
级	q	I-NAM	I-NAM\\
教	v	I-NAM	I-NAM\\
师	ng	E-NAM	E-NAM\\
1	x	B-NUM	B-NUM\\
0	x	I-NUM	I-NUM\\
4	x	E-NUM	E-NUM\\
人	n	S-UNI	S-UNI\\
}
{
}

\section{本章小结}

本章对于CRF++软件的编译安装以及基本使用方法进行了简述，并结合实例阐明了CRF++软件使用的特征模板的运作原理，根据原理与初等数学中数学命名实体的一些规律，制定了原子特征模板和组合特征模板。并完成了训练和测试的工作，最终得到了既包含人工数据也包含机器标注的初等数学概率与统计题数学命名实体的测试数据。
